﻿using DK.ITree;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DK.Tree
{
    public class BinaryTree<TKey, TData> : ITree<BinaryTreeNode<TKey, TData>, TKey, TData> where TKey : IComparable
    {
        public BinaryTreeNode<TKey, TData>? Root;
        public int Count;

        public BinaryTree() 
        {
            
        }

        public BinaryTreeNode<TKey, TData> AddAndReplace(TKey key, TData data)
        {
            return AddAndReplace(ref Root, key, data);
        }

        private BinaryTreeNode<TKey, TData> AddAndReplace(ref BinaryTreeNode<TKey, TData>? node, TKey key, TData data)
        {
            //终止条件
            if (node == null) 
            {
                node = new BinaryTreeNode<TKey, TData>(key, data);
                Count++;
                return node;
            } 

            //递归
            switch (key.CompareTo(node.Key))
            {
                case < 0://key小于当前节点时往下遍历左子树
                    return AddAndReplace(ref node.LeftChildNode, key, data);

                case > 0://key大于当前节点时往下遍历右子树
                    return AddAndReplace(ref node.RightChildNode, key, data);

                default://key等于当前节点时替换值
                    node.Value = data;
                    return node;
            }

        }

        public BinaryTreeNode<TKey, TData>? Get(TKey key)
        {
            return Get(Root, key);
        }
        public BinaryTreeNode<TKey, TData>? Get(BinaryTreeNode<TKey, TData>? node, TKey key)
        {
            //结束条件
            if (node == null) 
            {
                return null;
            }

            //递归
            switch (key.CompareTo(node.Key))
            {
                case < 0://key小于当前节点时往下遍历左子树
                    return Get(node.LeftChildNode, key);

                case > 0://key大于当前节点时往下遍历右子树
                    return Get(node.RightChildNode, key);

                default://key等于当前节点时返回
                    return node;
            }

        }

        public BinaryTreeNode<TKey, TData>? Remove(TKey key)
        {
            return Remove(ref Root, key);
        }

        public BinaryTreeNode<TKey, TData>? Remove(ref BinaryTreeNode<TKey, TData>? node, TKey key)
        {
            //结束条件
            if (node == null)
            {
                return null;
            }

            //递归查找
            switch (key.CompareTo(node.Key))
            {
                case < 0://key小于当前节点时往下遍历左子树
                    return Remove(ref node.LeftChildNode, key);

                case > 0://key大于当前节点时往下遍历右子树
                    return Remove(ref node.RightChildNode, key);

                default://key等于当前节点时进行删除
                    {
                        var removeNode = new BinaryTreeNode<TKey, TData>(node.Key, node.Value);

                        //为叶节点情况
                        if (node.LeftChildNode == null && node.RightChildNode == null)
                        {
                            node = null;
                        }

                        //度为1情况
                        else if ((node.LeftChildNode == null || node.RightChildNode == null) && (node.LeftChildNode != null || node.RightChildNode != null))
                        {
                            node = node.LeftChildNode ?? node.RightChildNode;
                        }

                        //度为2情况
                        else
                        {
                            var leftMaxNode = node.LeftChildNode;
                            var parent = node;
                            while (leftMaxNode.RightChildNode != null) 
                            {
                                parent = leftMaxNode;
                                leftMaxNode = leftMaxNode.RightChildNode;
                            }

                            if (leftMaxNode == node.LeftChildNode)
                                parent.LeftChildNode = null;
                            else
                                parent.RightChildNode = null;

                            leftMaxNode.RightChildNode = node.RightChildNode;
                            leftMaxNode.LeftChildNode = node.LeftChildNode;
                            node = leftMaxNode;
                        }

                        return removeNode;
                    }
            }
        }

    }
}
